import java.util.Collections;
static color defaultColor = 0;

public class  Polygon {

  ArrayList<PVector> points;
  EdgesTable edges;
  color bgColor;
  color fgColor; 
  float rotatedAngle = 0;


  public Polygon(ArrayList<PVector> points, color bgcolor, color fgcolor) {
    this.points = points;
    this.bgColor = bgcolor;
    this.fgColor = fgcolor;
  }

  public Polygon(color bgColor, color fgColor) {
    this(new ArrayList<PVector>(), bgColor, fgColor);
  }

  public Polygon(color allColor) {
    this(new ArrayList<PVector>(), allColor, allColor);
  }

  public Polygon() {
    this(new ArrayList<PVector>(), defaultColor, defaultColor);
  }

  
  public synchronized void setPoints(ArrayList<PVector> points) {
    this.points = points;
  }
  
  public synchronized ArrayList<PVector> getPoints() {
    return this.points;
  }
  
  /* This will add an edge formed by the provided point
   and the last point provided throug this method.
   */
  public synchronized void addPoint(PVector nextPoint) {
    this.points.add(nextPoint);
  }

  public synchronized void addPoint(int x, int y) {
    this.points.add(new PVector(x, y));
  }

  public synchronized Polygon clone() {
    Polygon copy = new Polygon();
    for (int i=0; i<points.size(); i++) {
      copy.addPoint(points.get(i));
    }
    return copy;
  }

  public void draw(PGraphics plot) {
    this.draw(plot, true);
  }

  public synchronized void draw(PGraphics plot, boolean complete) {
    color oldC = plot.get(0, 0);
    plot.stroke(0);
    if (points.size()>1) {
      int x1, y1;
      int x0 = (int)this.points.get(0).x;
      int y0 = (int)this.points.get(0).y;
      for (int i=1; i<points.size()+((complete)?1:0); i++) {
        x1 = (int)this.points.get(i%points.size()).x;
        y1 = (int)this.points.get(i%points.size()).y;
        plot.line(x0, y0, x1, y1);
        x0 = x1;
        y0 = y1;
      }
    }
    plot.stroke(oldC);
  }

  public void  draw() {
    this.draw(true);
  }

  public synchronized void draw(boolean complete) {
    color oldC = get(0, 0); 
    stroke(fgColor);
    if (points.size()>1) {
      int x1, y1;
      int x0 = (int)this.points.get(0).x;
      int y0 = (int)this.points.get(0).y;
      for (int i=1; i<points.size()+((complete)?1:0); i++) {
        x1 = (int)this.points.get(i%points.size()).x;
        y1 = (int)this.points.get(i%points.size()).y;
        line(x0, y0, x1, y1);
        x0 = x1;
        y0 = y1;
      }
    }
    stroke(oldC);
  }

  public  void rotate(float angle) {
    this.rotate(angle, new PVector(0, 0));
  }

  public  void rotate(float angle, PVector referencePoint) {
    this.transform(Matrix4.referenceRotation(angle, referencePoint));
    rotatedAngle += angle;
  }

  public  void translate(int x, int y) {
    this.transform(Matrix4.translation(x, y));
  }

  public  void scale(float percentageX, float percentageY, PVector referencePoint) {
    this.transform(Matrix4.referenceScaling(percentageX, percentageY, referencePoint));
  }

  public  void scale(float percentage) {
    this.scale(percentage, new PVector(0, 0));
  }

  public  void scale(float percentage, PVector referencePoint) {
    this.scale(percentage, percentage, referencePoint);
  }


  public synchronized void fill(PGraphics plot, color bgColor) {
    EdgesTable table = new EdgesTable(points);
    plot.stroke(bgColor);
    int y = table.getMinY();
    ArrayList<Edge> activeTable = table.getActiveEdgeTable(y);

    while (activeTable.size () > 0) {
      //draw
      for (int i=0; i<activeTable.size()-1; i+=2) {
        Edge e1 = activeTable.get(i);
        Edge e2 = activeTable.get(i+1);
        for (int x=e1.getMinX(); x<=e2.getMinX(); x++) {
          plot.point(x, y);
        }
      }
      y++;
      //update active table
      int size = activeTable.size();
      for (int i=0; i<size; i++) {
        Edge e = (Edge)activeTable.get(i);
        if (e.maxY <= y) {
          activeTable.remove(e);
          size--;
          i--;
        }
      }
      //update list
      ArrayList<Edge> next = table.getActiveEdgeTable(y);
      for (int i=0; i<activeTable.size(); i++) {
        Edge e = (Edge)activeTable.get(i);
        e.update();
      }
      if (next.size()>0) {
        activeTable.addAll(next);
        Collections.sort(activeTable);
      }
    }

  }

  public synchronized PVector getPoint(int i) {
    return points.get(i);
  }

  public synchronized int size() {
    return points.size();
  }

  private synchronized void transform(Matrix4 transformation) {
    for (int i=0; i < size(); i++) {
      PVector orig = this.getPoint(i);
      orig.z = 1; // For the projective transformations to work
      points.set(i, transformation.multiplyVector(orig));
    }
  }

  public synchronized ArrayList<Polygon> cut(Polygon window) {
    float x1, y1, wx0, wy0, wx1, wy1;
    ArrayList<Polygon> ret = new ArrayList<Polygon>(); 

    if (this.points.size()>1) {

      float x0 = (int)this.points.get(0).x;
      float y0 = (int)this.points.get(0).y;
      for (int i = 1; i < this.points.size()+1; i++) {
        x1 = (int)this.points.get(i%this.points.size()).x;
        y1 = (int)this.points.get(i%this.points.size()).y;

        ArrayList<PVector> normals = window.getNormals();
        float maxTe = -1.0f;
        float minTl = Float.MAX_VALUE;

        PVector p0 = new PVector(x0, y0);
        PVector p1 = new PVector(x1, y1);
        PVector D = PVector.sub(p1, p0);
        boolean p0In = true;
        boolean p1In = true;

        wx0 = (int)window.points.get(0).x;
        wy0 = (int)window.points.get(0).y;
        for (int j = 1; j < window.points.size()+1; j++) {
          wx1 = (int)window.points.get(j%window.points.size()).x;
          wy1 = (int)window.points.get(j%window.points.size()).y;

          //the interesting stuff
          PVector N = normals.get(j-1);
          PVector pe = new PVector(wx0, wy0);
          float denominator = N.dot(D);
          float numerator = N.dot(PVector.sub(p0, pe));
          p0In = p0In && (numerator<=0);
          p1In = p1In && (N.dot(PVector.sub(p1, pe))<=0);
          float t = numerator / (-1.0f*denominator);
          if (denominator < 0) { //Potencialmente entrante
            if (t>maxTe) maxTe = t;
          }
          else if (denominator > 0) {
            if (t<minTl) minTl = t;
          }

          wx0 = wx1;
          wy0 = wy1;
        }
        Polygon pol = new Polygon();
        if (p0In) {
          pol.addPoint(p0);
        }
        else if (maxTe < minTl && maxTe >= 0) {
          pol.addPoint(PVector.add(p0, PVector.mult(D, maxTe)));
        } 
        if (p1In) {
          pol.addPoint(p1);
        }
        else if (maxTe < minTl && minTl <= 1) { 
          pol.addPoint(PVector.add(p0, PVector.mult(D, minTl)));
        }
        if (pol.size()>0) ret.add(pol);

        x0 = x1;
        y0 = y1;
      }
    }

    return ret;
  }

  public ArrayList<PVector> getNormals() {
    PVector center = new PVector(0, 0);
    ArrayList<PVector> normals = new ArrayList<PVector>();


    while (normals.size () < points.size()) {
      for (int i=0; i < this.size(); i++) {
        center.add(this.getPoint(i));
      }
      center.mult(1.0f/this.size());
      //print("Center : ");
      //println(center);

      int wx0 = (int)this.points.get(0).x;
      int wy0 = (int)this.points.get(0).y;
      for (int j = 1; j < this.points.size()+1; j++) {
        int wx1 = (int)this.points.get(j%this.points.size()).x;
        int wy1 = (int)this.points.get(j%this.points.size()).y;

        PVector v = new PVector(wx0-wx1, wy0-wy1);

        float x, y;
        if (v.x ==0) {
          if (v.y ==0) {
            continue;
          }
          else {
            x = sqrt(1.0f/(1.0f+((v.x*v.x)/(v.y*v.y))));
            y = -1.0f*v.x*x/v.y;
          }
        }
        else {
          y = sqrt(1.0f/(1.0f+((v.y*v.y)/(v.x*v.x))));
          x = -1.0f*v.y*y/v.x;
        }

        PVector norm = new PVector(x, y);
        if (norm.dot(PVector.sub(center, new PVector(wx1, wy1))) >0) {
          norm.mult(-1.0f);
        }
        normals.add(norm);


        wx0 = wx1;
        wy0 = wy1;
      }
    }

    return normals;
  }

  public synchronized void setFgColor(color newColor) {
    this.fgColor = newColor;
  }

  public synchronized void setBgColor(color newColor) {
    this.bgColor = newColor;
  }

  public synchronized float getRotatedAngle() {
    return rotatedAngle;
  }
  
  public synchronized void cutByRigth(Polygon window) {
    
      Polygon ret = new Polygon(); 
      float wx0 = (int)window.points.get(0).x;
      float wy0 = 0;
      float wx1 = (int)window.points.get(1).x;
      float wy1= width;
      //Pasar por cada uno de las aristas del polígono
      float x0 = (int)this.points.get(0).x;
      float y0 = (int)this.points.get(0).y;
      
      for (int i = 1; i < this.points.size()+1; i++) {
           float x1 = (int)this.points.get(i%this.points.size()).x;
           float y1 = (int)this.points.get(i%this.points.size()).y;
           //println("arista "+x0+" "+y0+"-->"+x1+" "+y1);
             
                //Caso 2
                if(x0<wx0 && x1>wx0) {
                  if(Util.segIntersection(x0,y0,x1,y1,wx0,wy0,wx1,wy1)==2) {
                  PVector inter = Util.getIntersectionPoint();
                  if(inter != null) {
                      int x = round(inter.x);
                      int y = round(inter.y);
                      ret.addPoint(new PVector(x,y));
                      ret.addPoint(new PVector(x1,y1));
                  }
                  }
                }
                //Caso 3
                if(x0>wx0 && x1>wx0) {
                  ret.addPoint(new PVector(x1,y1));
                }
                //Caso 4 
                if(x0>wx0 && x1<wx0) {
                  if(Util.segIntersection(x0,y0,x1,y1,wx0,wy0,wx1,wy1)==2) {
                  PVector inter = Util.getIntersectionPoint();
                  if(inter != null) {
                      int x = round(inter.x);
                      int y = round(inter.y);
                      ret.addPoint(new PVector(x,y));
                  }
                  }
                }
           x0=x1;
           y0=y1;
      }
      this.setPoints(ret.getPoints());
  }
  
  public synchronized void cutBelow(Polygon window) {
    
      Polygon ret = new Polygon(); 
      float wx0 = 0;
      float wy0 = (int)window.points.get(1).y;
      float wx1 = height;
      float wy1= (int)window.points.get(2).y;
      //Pasar por cada uno de las aristas del polígono
      float x0 = (int)this.points.get(0).x;
      float y0 = (int)this.points.get(0).y;
      
      for (int i = 1; i < this.points.size()+1; i++) {
           float x1 = (int)this.points.get(i%this.points.size()).x;
           float y1 = (int)this.points.get(i%this.points.size()).y;
           //println("arista "+x0+" "+y0+"-->"+x1+" "+y1);
             
                //Caso 2
                if(y0>wy0 && y1<wy0) {
                  if(Util.segIntersection(x0,y0,x1,y1,wx0,wy0,wx1,wy1)==2) {
                  PVector inter = Util.getIntersectionPoint();
                  if(inter != null) {
                      int x = round(inter.x);
                      int y = round(inter.y);
                      ret.addPoint(new PVector(x,y));
                      ret.addPoint(new PVector(x1,y1));
                  }
                  }
                }
                //Caso 3
                if(y0<wy0 && y1<wy0) {
                  ret.addPoint(new PVector(x1,y1));
                }
                //Caso 4 
                if(y0<wy0 && y1>wy0) {
                  if(Util.segIntersection(x0,y0,x1,y1,wx0,wy0,wx1,wy1)==2) {
                  PVector inter = Util.getIntersectionPoint();
                  if(inter != null) {
                      int x = round(inter.x);
                      int y = round(inter.y);
                      ret.addPoint(new PVector(x,y));
                  }
                  }
                }
           x0=x1;
           y0=y1;
      }
      this.setPoints(ret.getPoints());
  }
  
  public synchronized void cutByLeft(Polygon window) {
    
      Polygon ret = new Polygon(); 
      float wx0 = (int)window.points.get(2).x;
      float wy0 = 0;
      float wx1 = (int)window.points.get(3).x;
      float wy1=width;
      //Pasar por cada uno de las aristas del polígono
      float x0 = (int)this.points.get(0).x;
      float y0 = (int)this.points.get(0).y;
      
      for (int i = 1; i < this.points.size()+1; i++) {
           float x1 = (int)this.points.get(i%this.points.size()).x;
           float y1 = (int)this.points.get(i%this.points.size()).y;
           //println("arista "+x0+" "+y0+"-->"+x1+" "+y1);
             
                //Caso 2
                if(x0>wx0 && x1<wx0) {
                  if(Util.segIntersection(x0,y0,x1,y1,wx0,wy0,wx1,wy1)==2) {
                  PVector inter = Util.getIntersectionPoint();
                  if(inter != null) {
                      int x = round(inter.x);
                      int y = round(inter.y);
                      ret.addPoint(new PVector(x,y));
                      ret.addPoint(new PVector(x1,y1));
                  }
                  }
                }
                //Caso 3
                if(x0<wx0 && x1<wx0) {
                  ret.addPoint(new PVector(x1,y1));
                }
                //Caso 4 
                if(x0<wx0 && x1>wx0) {
                  if(Util.segIntersection(x0,y0,x1,y1,wx0,wy0,wx1,wy1)==2) {
                  PVector inter = Util.getIntersectionPoint();
                  if(inter != null) {
                      int x = round(inter.x);
                      int y = round(inter.y);
                      ret.addPoint(new PVector(x,y));
                  }
                  }
                }
           x0=x1;
           y0=y1;
      }
      this.setPoints(ret.getPoints());
  }
  
  
   public synchronized void cutAbove(Polygon window) {
    
      Polygon ret = new Polygon(); 
      float wx0 = 0;
      float wy0 = (int)window.points.get(3).y;
      float wx1 = height;
      float wy1= (int)window.points.get(0).y;
      //Pasar por cada uno de las aristas del polígono
      float x0 = (int)this.points.get(0).x;
      float y0 = (int)this.points.get(0).y;
      
      for (int i = 1; i < this.points.size()+1; i++) {
           float x1 = (int)this.points.get(i%this.points.size()).x;
           float y1 = (int)this.points.get(i%this.points.size()).y;
           //println("arista "+x0+" "+y0+"-->"+x1+" "+y1);
             
                //Caso 2
                if(y0<wy0 && y1>wy0) {
                  if(Util.segIntersection(x0,y0,x1,y1,wx0,wy0,wx1,wy1)==2) {
                  PVector inter = Util.getIntersectionPoint();
                  if(inter != null) {
                      int x = round(inter.x);
                      int y = round(inter.y);
                      ret.addPoint(new PVector(x,y));
                      ret.addPoint(new PVector(x1,y1));
                  }
                  }
                }
                //Caso 3
                if(y0>wy0 && y1>wy0) {
                  ret.addPoint(new PVector(x1,y1));
                }
                //Caso 4 
                if(y0>wy0 && y1<wy0) {
                  if(Util.segIntersection(x0,y0,x1,y1,wx0,wy0,wx1,wy1)==2) {
                  PVector inter = Util.getIntersectionPoint();
                  if(inter != null) {
                      int x = round(inter.x);
                      int y = round(inter.y);
                      ret.addPoint(new PVector(x,y));
                  }
                  }
                }
           x0=x1;
           y0=y1;
      }
      this.setPoints(ret.getPoints());
  }
  
  
  public synchronized Polygon cutPolygon(Polygon window) {
    //Algoritmo Sutherland–Hodgman recorte de poligonos
    Polygon ret = new Polygon();
    if (this.points.size()>1) {
        this.cutByRigth(window);  
        this.cutBelow(window);
        this.cutByLeft(window);
        this.cutAbove(window);
    }
    return this;
  }
}

